131. 分割回文串

Similar Question

Solution Tips

方案一: 回溯 + 二元思路

var partition = function (s) {
    // 切割问题也可以理解为组合问题, 从集合里面选出连续的元素组合成 target 即可
    // 因为子串的长度不是固定的, 所以相当于需要动态 for, 可以考虑使用回溯暴力
    // 关键就是回文的判断还有剪枝了, 不然肯定会超时的
    const res = [];
    dfs([], 0, '', 0);
    return res;

    function dfs(part, partLen, cur, i) {
        // 是否构成回文串不是剪枝的理由, 有可能拼着拼着又成了, 所以只能是成了就 push
        if (i === s.length) {
            partLen === s.length && res.push(part)
            return;
        }

        // for (let i = index; i < s.length; i++) {
            // 单个元素一定是回文串, 所以 s[i] 可以直接 push
            // dfs([...part, s[i]], s[i], i + 1 )

        // 二元思路, 两种路线都得走, 因为必须全选, 所有不用 for 了, 单纯的二元思路为是否推入 part 即可
        const join = cur + s[i];
        if (isPalindrome(join)) {
            dfs([...part, join], partLen + join.length, '', i + 1);
        }

        dfs(part, partLen, join, i + 1);
        // }
    }

    function isPalindrome(s) {
        let n = s.length;
        let left = 0, right = n - 1;
        while (left < right) {
            if (s[left] !== s[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};
console.log(partition("aab"));

方案二: 回溯 + N 叉树思路

这个 n 叉树有点隐秘, 分叉在于每次截取不同的子串判断是否是回文串, 这个操作其实就是方案一的 cur 拼接与否

const isPalindrome = (s, l, r) => {
    for (let i = l, j = r; i < j; i++, j--) {
        if(s[i] !== s[j]) return false;
    }
    return true;
}

var partition = function(s) {
    const res = [], path = [], len = s.length;
    backtracking(0);
    return res;
    function backtracking(startIndex) {
        if(startIndex >= len) {
            res.push(Array.from(path));
            return;
        }
        for(let i = startIndex; i < len; i++) {
            if(!isPalindrome(s, startIndex, i)) continue;
            path.push(s.slice(startIndex, i + 1));
            backtracking(i + 1);
            path.pop();
        }
    }
};

方案三: 动态规划优化回文串判断